// Copyright 2013 Daniel de Kok
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.gitee.wsl.text.dictomaton

import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.lang.CompactIntArray
import com.gitee.wsl.lang.bits.BitSet
import com.gitee.wsl.text.format.format

/**
 *
 *
 * A finite state dictionary. Dictionaries of this type can are constructed
 * using [DictionaryBuilder.build].
 *
 *
 *
 * This class uses integers (int) for transition and state numbers.
 *
 * @author Daniel de Kok
 */
internal open class DictionaryImpl(
    stateOffsets: CompactIntArray,
    transitionChars: CharArray,
    transitionTo: CompactIntArray,
    finalStates: BitSet,
    nSeqs: Int
) : AbstractSet<String>(), Dictionary {
    // Offset in the transition table of the given state. E.g. d_stateOffsets[3] = 10
    // means that state 3 starts at index 10 in the transition table.
    protected val d_stateOffsets: CompactIntArray = stateOffsets

    // Note: we do not use an array of transition instances to represent the
    //       transition table, since this would require an additional pointer
    //       for each transition. Instead, we maintain the table as two parallel
    //       arrays.
    protected val d_transitionChars: CharArray = transitionChars
    protected val d_transitionTo: CompactIntArray = transitionTo
    protected val d_finalStates: BitSet = finalStates
    protected val d_nSeqs: Int = nSeqs

    override val size: Int
        get() = d_nSeqs

    override fun contains(element: String): Boolean {
        return containsSeq(element)
    }

    override fun containsAll(elements: Collection<String>): Boolean {
        for (o in elements) if (!contains(o)) return false

        return true
    }

    fun add(s: String): Boolean {
        throw UnsupportedOperationException()
    }

    
    fun addAll(c: Collection<String>): Boolean {
        throw UnsupportedOperationException()
    }

    
    fun clear() {
        throw UnsupportedOperationException()
    }

    
    override fun isEmpty(): Boolean {
        return size == 0
    }

    
    override fun isFinalState(state: Int): Boolean {
        return d_finalStates[state]
    }

   
    override fun iterator(): Iterator<String> {
        return DictionaryIterator()
    }

   
    override fun next(state: Int, c: Char): Int {
        val trans = findTransition(state, c)

        if (trans == -1) return -1

        return d_transitionTo.get(trans)
    }

    fun remove(o: String): Boolean {
        throw UnsupportedOperationException()
    }

    fun removeAll(c: Collection<*>?): Boolean {
        throw UnsupportedOperationException()
    }

    
    fun retainAll(c: Collection<*>?): Boolean {
        throw UnsupportedOperationException()
    }

    override fun toArray(): Array<Any?> {
        return toArray(arrayOfNulls<Any>(d_nSeqs))
    }

    override fun <T> toArray(array: Array<T>): Array<T> {
         val r: Array<T?> = if (array.size >= d_nSeqs) array as Array<T?> else arrayOfNulls(d_nSeqs)

        val iter = iterator()
        var idx = 0

        while (iter.hasNext()) {
            r[idx] = iter.next() as T?
            ++idx
        }

        if (r.size > d_nSeqs) r[size] = null

        return r as Array<T>
    }


    /**
     * Give the Graphviz dot representation of this automaton.
     *
     * @return
     */
    override fun toDot(): String {
        val dotBuilder = StringBuilder()

        dotBuilder.append("digraph G {\n")

        for (state in 0..<d_stateOffsets.size()) {
            for (trans in d_stateOffsets.get(state)..<transitionsUpperBound(state)) dotBuilder.append(
                String.format(
                    "%d -> %d [label=\"%c\"]\n",
                    state, d_transitionTo.get(trans), d_transitionChars[trans]
                )
            )

            if (d_finalStates.get(state)) dotBuilder.append(String.format("%d [peripheries=2];\n", state))
        }

        dotBuilder.append("}")

        return dotBuilder.toString()
    }

    
    override fun startState(): Int {
        return 0
    }

    
    override fun transitionCharacters(state: Int): Set<Char> {
        val transChars = HashSet<Char>()

        for (i in d_stateOffsets.get(state)..<transitionsUpperBound(state)) transChars.add(d_transitionChars[i])

        return transChars
    }

    private inner class DictionaryIterator : Iterator<String> {
        private val d_stack= ArrayList<StateStringPair>()

        init {
            d_stack.push(StateStringPair(0, ""))
        }

        
        override fun hasNext(): Boolean {
            return !(d_stack.isEmpty() || d_nSeqs == 0)
        }

        
        override fun next(): String {
            if (d_stack.isEmpty() || d_nSeqs == 0) throw NoSuchElementException()

            var pair: StateStringPair
            while (d_stack.isNotEmpty()) {
                pair = d_stack.pop()
                val state = pair.state
                val string = pair.string

                // Put states reachable through outgoing transitions on the stack.
                for (trans in transitionsUpperBound(state) - 1 downTo d_stateOffsets.get(state)) d_stack.push(
                    StateStringPair(
                        d_transitionTo.get(trans),
                        string + d_transitionChars[trans]
                    )
                )

                if (d_finalStates.get(state)) return string
            }

            // Impossible to reach.
            throw NoSuchElementException()
        }

        
        fun remove() {
            throw UnsupportedOperationException()
        }
    }

    private inner class StateStringPair(val state: Int, val string: String)

    /**
     * Calculate the upper bound for this state in the transition table.
     *
     * @param state
     * @return
     */
    protected fun transitionsUpperBound(state: Int): Int {
        return (if (state + 1 < d_stateOffsets.size()) d_stateOffsets.get(state + 1) else d_transitionChars.size)
    }

    /**
     * Find the transition for the given character in the given state. Since the
     * transitions are ordered by character, we can use a binary search.
     *
     * @param state
     * @param c
     * @return
     */
    protected fun findTransition(state: Int, c: Char): Int {
        var start: Int = d_stateOffsets.get(state)
        var end = transitionsUpperBound(state) - 1

        // Binary search
        while (end >= start) {
            val mid = start + ((end - start) / 2)

            if (d_transitionChars[mid] > c) end = mid - 1
            else if (d_transitionChars[mid] < c) start = mid + 1
            else return mid
        }

        return -1
    }

    /**
     * Check whether the dictionary contains the given sequence.
     *
     * @param seq
     * @return
     */
    private fun containsSeq(seq: String): Boolean {
        var state = 0
        for (i in 0..< seq.length) {
            state = next(state, seq[i])

            if (state == -1) return false
        }

        return d_finalStates[state]
    }

}
